from collections import defaultdict

T = int(input())
for _ in range(T):
    nt, k = map(int, input().split())
    cnts = defaultdict(int)
    for i in range(nt):
        a, b = map(int, input().split())
        cnts[a] += b
    cnt = 0
    for key, value in cnts.items():
        if value >= 3:
            cnt += 2
            cnts[key] -= 2
        else:
            cnts[key] = 0
            cnt += value
    cnts = list(sorted(cnts.values(), reverse=True))
    for i, cur in enumerate(cnts):
        if k <= 0:
            break
        if k < cur // 3:
            cnt += k * 3 - 2
            k = 0
            break
        else:
            cnt += cur // 3 * 3
            cnts[i] -= cur // 3 * 3
            k -= cur // 3
    if k > 0:
        for i, cur in enumerate(cnts):
            if k <= 0: break
            cnt += cur
            k -= 1
            cnts[i] = 0
    print(cnt if k <= 0 else -1)
